Sipser CH2 PROBLEMS'ANSWER 1-5

2.18

Let be a context-free language and be a regular language. Let be the PDA that recognizes , and be the DFA that recognizes . If is the set of states of and is the set of states of , we construct a PDA that recognizes with the set of states . will do what does and also keep track of the states of . It accepts a string if and only if it stops at a state , where is the set of accept states of and is the set of accept states of . Since is recognized by , it is context free.
Let be the regular language . If were a CFL then would be a CFL by part (a). However, , and Example 2.36 proves that is not context free. Thus is not a CFL.

2.19

The language consists of all strings of 's and 's that are not of the form for any integer . The CFG of is

2.20

设是由 PDA 接受的语言，是由 DFA 接受的语言。

我们构造新的 PDA ，具体如下：

状态集 : 的状态集包含的所有原始状态，以及一组用于“验证”阶段的复合状态。
起始状态 : 的起始状态与的起始状态相同。
接受状态集 : 的接受状态是这样一种复合状态：其中的部分处于接受状态，同时的部分也处于接受状态。
转移函数 : 转移函数包含三个部分，对应我们之前描述的两个阶段以及它们之间的切换。
1. 阶段一的转移（读取）: 对于任何在中的输入符号，模拟的行为。如果，其中，那么我们在中加入同样的转移：
2. 从阶段一到阶段二的切换: 当输入字符串读取完毕后，可以随时通过一个 -转移进入验证阶段。对于中的任意一个状态，我们添加一条 -转移，不改变栈的内容，进入一个复合状态。这个复合状态的第二部分是的起始状态，因为对的模拟需要从头开始。
3. 阶段二的转移（验证）: 在验证阶段，所有转移都是 -转移。每一步 -转移都代表猜测中的一个字符。对于任意复合状态，以及任意字符：如果有一个转移，并且有一个转移，那么我们就在中添加一条相应的 -转移：

工作原理解释

当得到输入时，它首先使用规则 (a) 来处理。这个过程完全模拟了的行为。在被完全读取后，假设的模拟到达了某个状态。
此时，可以使用规则 (b) 进行一次非确定性的 -转移，从状态跳转到复合状态，并进入验证阶段。
在验证阶段，进行一系列的 -转移（规则 c）。每一次这样的转移都对应于非确定性地选择一个字符，并同时更新的模拟状态（从到）和的模拟状态（从到）。
如果存在一串非确定性的选择（即一串字符），使得的模拟从最终到达了某个接受状态（这表明），并且的模拟从状态最终也到达了某个接受状态（这表明），那么将会到达复合状态。
根据我们的定义，是的一个接受状态。因此，输入字符串被接受。

2.21

该语言可以形式化地定义为。

一、上下文无关文法 (CFG)

我们提出的上下文无关文法，其产生式规则如下：

二、正确性证明

证明分为两部分：可靠性 (Soundness) 和 完备性 (Completeness)。

1. 可靠性证明 ()

目标：证明由文法生成的任何字符串都满足。我们对派生步骤的长度进行归纳。

基础情况: 派生长度为 1。。对于，，满足。
归纳假设: 假设所有派生长度小于的派生所生成的字符串都满足。
归纳步骤: 考虑长度为的派生。
- 若第一步为，则。的派生长度小于，由归纳假设，且。因此，。
- 若第一步为，则。满足归纳假设。因此：显然，。
- 对于规则和，可以通过完全相同的代数运算验证该性质得以保持。

因此，所有由生成的字符串都在中。

2. 完备性证明 ()

目标：证明语言中的任何字符串都可以由文法生成。我们对字符串的长度进行强归纳。为方便证明，定义函数。等价于。

基础情况: 。则。可以通过规则生成。
归纳假设: 假设所有在中且长度小于的字符串都可以由生成 ()。
归纳步骤: 考虑且。
- 情况 A: 是可分解的 (Decomposable) 若能被分解为，其中均为中的非空字符串。因为且，根据归纳假设，且。因此，可以使用规则生成：。
- 情况 B: 是不可分解的 (Indecomposable) 若不可分解，意味着对于的任何非空真前缀，都有 (即 )。
  - 若以 '' 开头: 的形式必然是或。
    1. 计算的特征值：若，则；若，则。
    2. 对进行分解：令是的最长的、属于的前缀 ()。将写为。
    3. 分析剩余部分：由于的最长性，没有任何非空前缀属于。
      - 当时，必须以开头，可写作，解得，即。
      - 当时，必须以开头，可写作，解得，即。
    4. 还原 w 的结构：
      - 变为，对应规则
      - 变为，对应规则
  - 如果以 '' 开头: 。则，所以。对于的任何真前缀（其中是的前缀），。
    - 考虑在中，函数的值从变化到。因为函数值的变化步长为 +1 (遇到'a') 或 -2 (遇到'b')，所以路径上必然存在一点，使得函数值等于1。令是的最短的非空前缀，满足。
    - 这个必须以 'a' 结尾（否则值无法从0或负数精确到达1）。所以，其中。所以。现在我们有。代入可得。
    - 对应用同样的逻辑，它必须以 'a' 结尾，即，其中。所以。
    - 因此，我们证明了，其中。
    - 这意味着。根据归纳假设，和。所以我们可以生成：。

在不可分解的所有情况下，都可以被分解为更小的、属于的字符串（它们根据归纳假设可以由生成），并嵌套在一个产生式规则中。因此，也可以被生成。

2.22

问题： 证明语言 $且$ 是一个上下文无关语言。

证明：

我们可以将语言分解为两个子语言和的并集，即。上下文无关语言对并集运算是封闭的，因此我们只需证明和都是上下文无关语言即可。

这个语言（字符串长度不相等）是上下文无关的，因为我们可以构造一个确定性下推自动机（DPDA）来接受它：
- 读取 # 左边的，每读一个符号就向栈中推入一个标记。
- 读取 # 右边的，每读一个符号就弹出一个标记。
- 如果输入结束时，栈不为空（），则受理。
- 如果在读取的过程中栈已变空但仍有剩余（），则受理。因此，是上下文无关语言。
$且$ 这个语言（长度相等但内容不同）也是上下文无关的，因为我们可以构造一个非决定性下推自动机（NPDA）来接受它：
- NPDA 非决定性地猜测一个位置，并认定和在该位置的字符不同（）。
- 执行逻辑：
  - 自动机读取的前个字符，但不使用栈。
  - 读取第个字符，并利用有限状态（例如，转移到“记忆0”或“记忆1”等特定状态）将其“记忆”下来。
  - 读取的后缀（之后的所有字符），每读一个字符就向栈中推入一个标记。
  - 读取 # ，然后读取的前个字符，同样不使用栈。
  - 读取的第个字符，并与状态中记忆的比较。如果两者相同，则此路不通；如果不同，则继续。
  - 读取的后缀，每读一个字符就从栈中弹出一个标记。
- 如果输入结束时栈正好变空，说明和的前后缀长度均对应相等，总长度也相等，且在位置存在不匹配。因此，字符串被受理。
- 所以，是上下文无关语言。

因为和都是上下文无关语言，所以它们的并集也必然是上下文无关语言。证明完毕。

ZC's Blog